package com.chapter1.basic.analysis;

/** 
 * @ClassName: QuickUnion 
 * @Description: quickUnion是对quickFind的一种改良
 * @author minjun minjun@bw30.com
 * @date 2015-2-13 下午2:23:05 
 *  
 */
public class QuickUnionImprove extends QuickUnion{

	/**
	 * 所有根节点所包含的分量数
	 */
	private int[] size;

	/**
	 * 初始化所有触点
	 */
	public QuickUnionImprove(int count) {
		super(count);
		size=new int[count];
		for(int i=0;i<count;i++){
			size[i]=1;
		}
	}

	/**
	 * 
	* @Title: union 
	* @Description: 判断给定的两个数是否连通--如果不连通，则进行连通；如果已经相连，不作任何事 。
	* 相对于quickfind，优化了union方法
	* @param @param m
	* @param @param n    设定文件 
	* @return void    返回类型 
	* @throws
	 */
	public void union(int m, int n) {
		int i = find(m);
		int j = find(n);

		//若拥有相同的根节点，表示两者连通
		if (i == j) {
			return;
		}
		
		if(size[i]<size[j]){
			//将小树连到大树上面
			array[i]=j;
			size[j]+=size[i];
		}else{
			array[j]=i;
			size[i]+=size[j];
		}
		count--;
	}
	
}
